/* 将给定的二叉树转化为等价的中缀表达式 */
#include <iostream>
#include "BiTreefun.h"
using namespace std;

// 二叉树转中缀表达式 -- 方法一
void fun(BTNode *p, int deep)
{
  // 二叉树不为空
  if (p != NULL)
  {
    // 如果不是叶子结点
    if ((p->lchild || p->rchild) && deep > 1)
      cout << "(";
    
    // 左子树转中缀表达式
    if (p->lchild != NULL)
      fun(p->lchild, deep + 1);
    
    // 当前结点值
    cout << p->data;
    
    // 右子树转中缀表达式
    if (p->rchild != NULL)
      fun(p->rchild, deep + 1);
    
    // 如果不是叶子结点
    if ((p->lchild || p->rchild) && deep > 1)
      cout << ")";
  }
}

// 二叉树转中缀表达式 -- 方法二
void fun2(BTNode *p, int deep)
{
  // 二叉树不为空
  if (p != NULL)
  {
    // 如果不是叶子结点
    if ((p->lchild || p->rchild) && deep > 1)
      cout << "(";
    
    ++deep;
    
    // 左子树转中缀表达式
    if (p->lchild != NULL)
      fun2(p->lchild, deep);
    
    // 打印结点值
    cout << p->data;
    
    // 右子树转中缀表达式
    if (p->rchild != NULL)
      fun2(p->rchild, deep);
    --deep;
    
    // 如果不是叶子结点
    if ((p->lchild || p->rchild) && deep > 1)
      cout << ")";
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 二叉树转中缀表达式
  fun2(T, 1);
  return 0;
}
